#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;


//方法1，超时
// class Solution {
// public:
//     int nthUglyNumber(int n) {
//         if(n<=6){
//             return n;
//         }
//         int sum = 6;
//         vector<bool> dp(7,true);
//         int i = 7;
//         while(true){
//             if((i%2==0&&dp[i/2])||(i%3==0&&dp[i/3])||(i%5==0&&dp[i/5]))
//                 dp.push_back(true);
//             else{
//                 dp.push_back(false);
//             }
//             if(dp[i]){
//                 sum++;
//             }
//             if(sum==n){
//                 return i;
//             }
//             ++i;
//         }
//         return 0;
//     }
// };

//方法2
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n,0);
        int a,b,c;
        dp[0] = 1;
        a = b = c= 0;
        for(int i = 1;i<n;++i){
            int temp = min(dp[a]*2,dp[b]*3);
            dp[i] = min(temp,dp[c]*5);
            (dp[i]==dp[a]*2)? ++a:a;
            (dp[i]==dp[b]*3)? ++b:b;
            (dp[i]==dp[c]*5)? ++c:c;
        }
        return dp[n-1];

    }
};

int main(){
    Solution S;
    cout<<S.nthUglyNumber(10)<<endl;
}

